﻿//438. 找到字符串中所有字母异位词
//给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
//异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。
class Solution {
public:
    vector<int> findAnagrams(string s, string p)
    {

        vector<int> ans;
        if (s.size() < p.size())
        {
            return ans;
        }
        vector<int> pcount(26), scount(26);
        for (int i = 0; i < p.size(); i++)
        {
            pcount[p[i] - 'a']++;
            scount[s[i] - 'a']++;
        }
        if (pcount == scount)
        {
            ans.push_back(0);
        }
        for (int i = 0; i < s.size() - p.size(); i++)
        {

            scount[s[i] - 'a']--;
            scount[s[i + p.size()] - 'a']++;
            if (pcount == scount)
            {
                ans.push_back(i + 1);
            }
        }
        return ans;
    }
};